\subsubsection{Solución elegida}
Para la solución se trato de buscar algún tipo de relación
 entre las joyas y sus costos para poder establecer un coeficiente 
 que permitiera dadas 2 joyas con sus costos, establecer cual convenía
 producir primero.
 Luego de varios ejemplos y de tratar de demostrar formalmente que existía
 ese coeficiente se decidió utilizar un algoritmo de ordenamiento de los ya conocidos
 para poder cumplir con la cota de complejidad requerida por el enunciado.\\
 Se pedía plantear una solución con una complejidad menor a $O(n^{2})$, por esto
 decidimos usar merge sort para poder cumplir con esa cota, merge sort
 nos posibilita en $O(n*log(n))$ poder hallar la solución óptima. 

 Se realiz\'o una modificación en el algoritmo de ordenamiento para 
 respetar la relación de orden siguiente:

\newline Sean $i$, $j$ los índices de dos elementos del arreglo de joyas, $i < j$ , el elemento $i$ es menor a $j$ si $\frac{d_{i}}{t_{i}}$ $\ge$ $\frac{d_{j}}{t_{j}}$.
Con esta relación de orden obtuvimos una forma óptima de ordenar las joyas para obtener la menor perdida. Esto será demostrada en la sección Demostraci\'on.

\subsubsection{Ejemplos}

Dada la siguiente lista [$<$1,4$>$, $<$1,6$>$, $<$3, 7$>$], donde cada tupla representa la pérdida y el tiempo en el que se construye cada joya respectivamente.\\
Como el objetivo es encontrar el orden óptimo para construir las joyas, veamos cuál es el costo total ordenando la lista de diferentes maneras.\\
Primero calculamos el costo total usando la lista de joyas sin reordenar. \\ \\
Fabricar la primer joya costaría:\\ 
(1 + 1 + 3 ) * 4  = 20\\
La segunda: \\
(1 + 3) * 6 = 24\\
Y la tercera:\\
3 * 7 = 21\\
Luego la pérdida total sería 20 + 24 + 21 = 65.\\

Siguiendo el mismo razonamiento, calculamos el costo total para la secuencia ordenada de todas las formas posibles:\\ \\
Para [$<$1,4$>$, $<$3, 7$>$, $<$1,6$>$]: \\
20 + 28 + 6 = 54 \\ \\
Para [$<$1,6$>$, $<$1,4$>$, $<$3, 7$>$]:\\
30 + 16 + 21 = 67\\ \\
Para [$<$1,6$>$, $<$3, 7$>$, $<$1,4$>$]:\\
30 + 28 + 4 = 62\\ \\
Para [$<$3, 7$>$, $<$1,6$>$, $<$1,4$>$]:\\
35 + 12 + 4 = 51\\ \\
Para [$<$3, 7$>$, $<$1,4$>$, $<$1,6$>$]:\\
35 + 8 + 6 = 49\\

Obtuvimos que la forma óptima de ordenar las joyas es [$<$3, 7$>$, $<$1,4$>$, $<$1,6$>$], ya que acarrea el menor costo total. Este resultado es esperado, pues el orden de esa secuencia es el obtenido al aplicar la relación de orden planteada para solucionar el problema.

\subsubsection{Demostración}
Sabemos que el costo de construir la joya i es $t_{i}$*$\sum\limits$$_{j=i}^n d_{j}$, siendo $t_{i}$ la cantidad de días que lleva construirla y $\sum\limits$$_{j=i}^n d_{j}$ la suma de los costos de las joyas que no se construyeron todavía. Por lo tanto la perdida de construir todas las n joyas ser\'ia sumar la perdida para cada joya, esto mismo puede representarse con la siguiente formula $\sum\limits$$_{j=1}^n t_{j}$$\sum\limits$$_{i=j}^n d_{i}$, siendo esta la fórmula de la perdida que debemos minimizar definiendo el orden de las joyas.

Sea f(s) = $\sum\limits$$_{j=1}^n t_{j}$$\sum\limits$$_{i=j}^n d_{i}$  la función que dada una secuencia de joyas devuelve la pérdida total y sea $\mathcal{S}$ una secuencia optima(la que minimiza f(s)). 
Supongamos ahora que en esta secuencia hay dos elementos que no están ordenados según el orden indicado anteriormente, en particular veamos el caso con dos elementos consecutivos.\\
Sean k y k+1 los índices  que no respetan el orden en base 
al coeficiente propuesto\\ tal que $\frac{d_{k{_S}}}{t_{k{_S}}}$ $<$ $\frac{d_{k+1{_S}}}{t_{k+1{_S}}}$.\\
Sea $\mathcal{S}$$_1$ la secuencia que resulta de ordenar esos dos elementos.
Sabiendo que S es una secuencia  optima por hipotesis, veamos que se cumple que : 

\textbf{Paso uno:}
f($\mathcal{S}$$_1$) $\ge$ f($\mathcal{S}$)
\begin{center}
f($\mathcal{S}$$_1$) $\ge$ f($\mathcal{S}$)
 $\iff$ $\sum\limits$$_{l=1}^n t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ $\ge$ $\sum\limits$$_{j=1}^n t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^n d_{i}$$_\mathcal{S}$\newline
\end{center}

Es igual que  \\
\textbf{Paso dos:}\\

\begin{center}
$\sum\limits$$_{l=1}^{k-1} t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ $\sum\limits$$_{m=k+1}^n d_{m}$$_\mathcal{S}$$_1$  +  $\sum\limits$$_{l=k+2}^n t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ 
\\ $\ge$  \\
$\sum\limits$$_{j=1}^{k-1} t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^n d_{i}$$_\mathcal{S}$ + $t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k}^n d_{i}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+1}^n d_{i}$$_\mathcal{S}$  + $\sum\limits$$_{j=k+2}^n t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^n d_{i}$$_\mathcal{S}$
\end{center}


Sabemos por hipótesis que $\mathcal{S}$$_1$  resulta de intercambiar los elementos k y k+1 de la secuencia $\mathcal{S}$, por lo que la construcción desde la primer joya hasta la joya k-1 son iguales en ambas secuencias, ya que como las joyas k y k+1 no se construyeron todavía aparecen ambas en las sumatorias que corresponden a la función de perdida de las secuencias $\mathcal{S}$ y $\mathcal{S}$$_1$ de las joyas 1 a k-1. \newline
Por otra parte cuando ya se construyeron las joyas k y k+1 las secuencias de joyas pendientes quedan son iguales con lo que la perdida de estas subsecuencias es la misma.\\
\textbf{Paso tres:}
Dicho de otra forma:\\	
a) $\sum\limits$$_{l=1}^{k-1} t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ = $\sum\limits$$_{j=1}^{k-1} t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^n d_{i}$$_\mathcal{S}$ \newline
\\
b) $\sum\limits$$_{l=k+2}^n t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ = $\sum\limits$$_{j=k+2}^n t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^n d_{i}$$_\mathcal{S}$
\newline

\textbf{Paso cuatro:}Por lo tanto podemos cancelar los términos en nuestra desigualdad y nos quedar\'ia.\\

\begin{center}
 $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+1}^n d_{m}$$_\mathcal{S}$$_1$ 
$\ge$
$t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k}^n d_{i}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+1}^n d_{i}$$_\mathcal{S}$\\
\end{center}

A su vez en cada una de las sumatorias puedo separar los elementos que me interesa comparar entre ambas secuencias para eliminar los que son iguales entre ambas en la desigualdad.\newline


\hspace*{-1.5em}\textbf{Paso cinco:} En la secuencia $\mathcal{S}$\\

\hspace*{-1.5em}$t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k}^n d_{i}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+1}^n d_{i}$$_\mathcal{S}$ = \newline 
\hspace*{3.5em}$t_{k}$$_\mathcal{S}$ *$d_{k}$$_\mathcal{S}$  + $t_{k}$$_\mathcal{S}$ * $d_{k+1}$$_\mathcal{S}$ + $t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+2}^n d_{i}$$_\mathcal{S}$ +  $t_{k+1}$$_\mathcal{S}$ * $d_{k+1}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+2}^n d_{i}$$_\mathcal{S}$
\newline

\hspace*{-1.5em} \textbf{Paso seis:} En la secuencia nos quedaria $\mathcal{S}$$_1$ \\

\hspace*{-1.5em}$t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+1}^n d_{m}$$_\mathcal{S}$$_1$ = \\
\hspace*{3.5em} $t_{k}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$ +  $t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$\\


\hspace*{-1.5em} \textbf{Paso siete:} A su vez por hipotesis sabemos que se intercambiaron los elementos k y k+1 , por lo tanto tenemos que

\begin{center}
$t_{k}$$_\mathcal{S}$ =  $t_{k+1}$$_\mathcal{S}$$_1$ y $t_{k+1}$$_\mathcal{S}$ = $t_{k}$$_\mathcal{S}$$_1$

$d_{k}$$_\mathcal{S}$ =  $d_{k+1}$$_\mathcal{S}$$_1$ y $d_{k+}$$_\mathcal{S}$ = $d_{k}$$_\mathcal{S}$$_1$
\end{center}

\hspace*{-1.5em} \textbf{Paso ocho:} - Reemplazando en la desigualdad nos quedaría

\begin{center}
$t_{k}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$ +$t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$ \\
$\ge$ \\ $t_{k+1}$$_\mathcal{S}$$_1$  *$d_{k+1}$$_\mathcal{S}$$_1$  + $t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{i=k+2}^n d_{i}$$_\mathcal{S}$$_1$ +  $t_{k}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+2}^n d_{i}$$_\mathcal{S}$
\end{center}
Ahora puedo cancelar los términos que son iguales en ambos lados de la igualdad.\newline

\hspace*{-1.5em}\textbf{Paso nueve} - Cancelo las sumatorias que son iguales en ambos lados de la desigualdad

\begin{center}
$t_{k}$$_\mathcal{S}$$_1$*$d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$*$d_{k
+1}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ $\ge$ $t_{k+1}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$  + $t_{k+1}$$_\mathcal{S}$$_1$*$d_{k}$$_\mathcal{S}$$_1$ +  $t_{k}$$_\mathcal{S}$$_1$*$d_{k}$$_\mathcal{S}$$_1$
\end{center}
\\

\hspace*{-1.5em}\textbf{Paso diez} - Cancelo los otros términos iguales

\begin{center}
$t_{k}$$_\mathcal{S}$$_1$ $d_{k+1}$$_\mathcal{S}$$_1$ $\ge$ $t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$
\end{center}

\hspace*{-1.5em}\textbf{Tercer once}- como $t_{k}$ y $t_{k+1}$ enteros positivos paso dividiendo.


\begin{center}
$\frac{d_{k+1{_S_1}}}{t_{k+1{_S_1}}}$ $\ge$ $\frac{d_{k{_S_1}}}{t_{k{_S_1}}}$.
\end{center}
Que es lo mismo que decir\\
\begin{center}
 $\frac{d_{k{_S}}}{t_{k{_S}}}$ $\ge$ $\frac{d_{k+1{_S}}}{t_{k+1{_S}}}$.\\
\end{center}
Se puede ver que llegamos a la conclucion $\frac{d_{k{_S}}}{t_{k{_S}}}$ $\ge$ $\frac{d_{k+1{_S}}}{t_{k+1{_S}}}$,
esto es absurdo por que en la hipotesis se planteo que $\frac{d_{k{_S}}}{t_{k{_S}}}$ $<$ $\frac{d_{k+1{_S}}}{t_{k+1{_S}}}$ por lo tanto
$S$ no es optima y f($\mathcal{S}$) $>$ f($\mathcal{S}$$_1$) o bien si $S$ es optima no puede pasar que 2 elementos 
consecutivos esten desordenados. En el caso que $\frac{d_{k{_S}}}{t_{k{_S}}}$ $=$ $\frac{d_{k+1{_S}}}{t_{k+1{_S}}}$ llego a que no importa en que orden ponga esas 
dos joyas porque la secuencia da la misma perdida, entonces existe mas de una solucion optima ya que al intercambiar el elemento de lugar por uno que de igual 
coeficiente en el orden obtengo una nueva secuencia.
Como partimos de la optimalidad de $S$ luego no puede haber 2 items desordenados en $S$, 
si en $S$ exitieran 2 elementos no contiguos desordenados, por transitividad exitiria un elemento 
intermedio que estaria desordenado con su continguo y en ese caso aplicaria la misma demostracion anterior concluyendo asi que
si $S$ es optima $S$ no puede estar desordenada.\\

Veamos ahora que si $S$ esta ordenada por el coeficiente que proponemos, entonces $S$ es optima. \\

Ahora por induccion puedo demostrar que una secuencia ordenada me lleva
a una solucion optima.\\
Lo hago con induccion en la cantidad de  joyas.\\
P(1) = trivial\\
P(K) = ordenando K joyas llego a una solucion de K joyas optima\\
P(K+1) = ordenando K+1 joyas llego a una solucion optima con K+1 joyas.\\
\\
Supongamos que se cumple P(K), veamos que se cumple P(K+1).\\
Si tengo K+1 joyas y retiro una sé, por HI, que ordenando las K fichas 
voy a llegar a una solucion optima. Tratemos ahora de agregar a 
K fichas ordenadas una ficha mas y mantener la optimalidad de la solucion.\\
\\ 
Supongamos que mi ficha la inserto desordenada, es evidente que eso no lleva a una solucion 
optima por lo visto en la demostración anterior ya que la formula de perdida de la secuencia va a ser mayor a la formula de la secuencia ordenada.
Luego inserto la ficha ordenada.\\ 
Ahora surge la posibilidad de que haya elementos con coeficientes repetidos entonces
manteniendo el orden tengo varios lugares donde puedo insertar mi elemento
en cualquier posicion que mantenga el orden.
Se ve que el orden de produccion de joyas con coeficiente iguales no altera la funcion de 
perdida porque la diferencia de las perdidas de las secuencias da 0 en la comparacion del paso uno de la demostracion anterior por ser todos los terminos iguales.
Por lo tanto en cualquier posicion ordenada que inserte mi ficha K+1 voy a llegar a mi solucion optima.
%Si $S$ no fuera optima y estuviera ordenada quiere decir que, dado que optima $\rightarrow$  ordenada, 
%que hay una permutacion de elementos con igual coeficiente que hace que $S$ pueda ser optima. \\


% En la demostracion primera se vio que optimo $\rightarrow$ ordenada, esto es lo mismo
% que decir entonces decir que $\neg$ ordenada $\rightarrow$  $\neq$ optima
% es falso, osea negar la contrareciproca, absurdo.
% Luego ordenada $\rightarrow$ optima.

% Pero esto es lo mismo que negar la afirmacion  $\neg$ optima $\rightarrow$ $\neg$ ordenada, cosa
% que mas arriba en la primer demostracion quedo probado.\\


% $S$ o bien f($\mathcal{S}$) $\le$ f($\mathcal{S}$$_1$) Esto tambien quiere decir que f($\mathcal{S}$$_1$) $\le$ f($\mathcal{S}$), pero esto es absurdo ya que por hipotesis dijimos que el elemento de la posicion k+1 era menor al elemento de la posicion k, por lo que encontramos una secuencia que da menor perdida, y esta es la secuencia ordenada.
% Caso contrario podria pasar que $\frac{d_{k{_S}}}{t_{k{_S}}}$ = $\frac{d_{k+1{_S}}}{t_{k+1{_S}}}$ siendo asi otra solucion optima si se intercambian los elementos, mismo podria pasar con otros elementos de la secuencia valida, pero esto no afectaria ya que las funciones de perdida serian iguales y ambas serian soluciones optimas.
% Como vimos en la demostracion f($\mathcal{S}$$_1$) $\le$ f($\mathcal{S}$), por lo tanto $\mathcal{S}$ no es una solucion optima ya que encontre una solucion mejor, mismo pasa que si tengo la solucion ordenada $\mathcal{S}$$_1$ y desordeno esos dos elementos $\mathcal{S}$$_1$ deja de ser optima, esto a su vez quiere decir que si no es optima entonces no esta ordenada.
% Por lo tanto la secuencia es optima si y solo si esta ordenada por la relacion de orden propuesta.

% La demostración se realiza en base a dos elementos consecutivos pero podria pasar que los elementos intercambiados no lo sean, por transitividad en la relacion de orden tampoco se cumpliria para los vecinos a esos elementos cambiados por lo que la demostracion sería valida tambien en esos casos.



